package cxydmmszl.chapter08.t127;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;

/**
 * <li style="color: red;">Prob</li>
 * 计算数组的小和
 * <li style="color: green;">Desc</li>
 * 数组小和的定义如下：<br/>
 * 例如，数组s = [1, 3, 5, 2, 4, 6]，<br/>
 * 在 s[0] 的左边小于或等于 s[0] 的数的和为 0；<br/>
 * 在 s[1] 的左边小于或等于 s[1] 的数的和为1；<br/>
 * 在 s[2] 的左边小于或等于 s[2] 的数的和为 1+3=4；<br/>
 * 在 s[3] 的左边小于或等于 s[3] 的数的和为1；<br/>
 * 在s[4]的左边小于或等于 s[4] 的数的和为 1+3+2=6；<br/>
 * 在 s[5] 的左边小于或等于 s[5] 的数的和为 1+3+5+2+4=15。<br/>
 * 所以s的小和为 0+1+4+1+6+15=27。
 * <br/>给定一个数组 s，实现函数返回s的小和。
 * <br/><br/>[要求]<br/>时间复杂度为O(nlogn)，空间复杂度为O(n)
 * <br/><br/>备注：<br/>1⩽N⩽10^5, −100⩽arr[i]⩽100
 * <li style="color: green;">Input</li>
 * 第一行有一个整数N。表示数组长度
 * 接下来一行N个整数表示数组内的数
 * <li style="color: green;">Output</li>
 * 一个整数表示答案
 * <li style="color: blue;">Link</li> CD21
 *
 * @author habitplus
 * @since 2021-10-07 21:12
 */
public class Main {
    static StreamTokenizer st =
            new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));

    static int nextInt() {
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    public static void main(String[] args) {
        int n = nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = nextInt();
        }

        long ans = getSmallSum(arr);
        System.out.println(ans);

    }

    private static long getSmallSum(int[] arr) {
        if (arr == null || arr.length < 2) {
            return 0;
        }
        // 利用归并排序过程来求解
        int n = arr.length;
        int[] aux = new int[n];
//        System.arraycopy(arr, 0, aux, 0, n);
        return mergeSort(arr, aux, 0, n - 1);
    }

    /**
     * 归并排序过程，并返回 arr[l,r] 的小和
     *
     * @param arr 待排序数组
     * @param aux 辅助数组
     * @param l   左边界
     * @param r   右边界
     * @return arr[l, r] 的小和
     */
    private static long mergeSort(int[] arr, int[] aux, int l, int r) {
        // 只有一个数，返回 0
        if (l >= r) return 0;

        int m = (l + r) / 2;
        return mergeSort(arr, aux, l, m) + mergeSort(arr, aux, m + 1, r) + merge(arr, aux, l, m, r);
    }

    /**
     * 合并 arr[l,m] 和 arr[m+1, r]，并返回两个子数组之间的数组小和
     *
     * @param arr 待排序数组
     * @param aux 辅助数组
     * @param l   左边界
     * @param m   中点（二分）
     * @param r   右边界
     * @return 两个有序子数组之间的数组小和
     */
    private static long merge(int[] arr, int[] aux, int l, int m, int r) {
        if (l >= r) return 0;

        int i = l, j = m + 1, k = l;
        long smallSum = 0;
        while (i <= m || j <= r) {
            if (i > m) {
                aux[k++] = arr[j++];
            } else if (j > r) {
                aux[k++] = arr[i++];
            } else {
                if (arr[i] > arr[j]) {
                    aux[k++] = arr[j++];
                } else {
                    // 这里会产生小和
                    smallSum += (long) arr[i] * (r - j + 1);
                    aux[k++] = arr[i++];
                }
            }
        }

        System.arraycopy(aux, l, arr, l, r - l + 1);
        return smallSum;
    }
}
